package com.ocean.everyday.d005_minimumsidewayjumps;

/**
 * https://leetcode.cn/problems/minimum-sideway-jumps/
 * <p>
 * 最少侧跳次数
 */
public class MinimumSidewayJumps {

    public static void main(String[] args) {
        MinimumSidewayJumps sidewayJumps = new MinimumSidewayJumps();
        int[] nums = {0,1,2,3,0};
        int i = sidewayJumps.minSideJumps(nums);
        System.out.println(i);
        int[] nums2 = {0,1,1,3,3,0};
        System.out.println(sidewayJumps.minSideJumps(nums2));
    }


    /**
     * d[i][j] = d[i-1][j]  j != obstacles[i] -1
     * <p>
     * minCnt = min(d[i][0],d[i][1],d[i][2])
     * d[i][j]=min(d[i][j],minCnt+1)
     * <p>
     * d[n][0] = min(d[n][0],)
     * d[n][1]
     * d[n][2]
     * <p>
     * 到达第二个点(obstacles下标为1) 有以下可能：
     * 1 从第0个点直接跳
     * 2 向上侧跳 再直跳
     * 3 向下侧跳 再直跳
     * <p>
     * 到达第3个点 也有3种可能
     * 所以 d[i][j]=min(d[i][j],minCnt+1)
     * 其中：minCnt = min(d[i][0],d[i][1],d[i][2])
     * <p>
     * 循环每个点 判断当前所在点有没有障碍 计算到达当前点的最小侧跳次数
     *
     * @param obstacles
     * @return
     */
    public int minSideJumps(int[] obstacles) {
        final int INF = 0x3fffffff;
        int n = obstacles.length - 1;
        int[] d = new int[3];
        d[0] = 1; // 从第2条道开始 到第1条道有一次侧跳
        d[1] = 0;
        d[2] = 1; //  从第2条道开始 到第3条道有一次侧跳
        // 从第2个点开始计算
        for (int i = 1; i <= n; i++) {
            // 先判断当前的点 的3条道路上有没有障碍
            int min = INF;
            for (int j = 0; j < 3; j++) {
                if (obstacles[i] - 1 == j) {
                    // 说明有障碍
                    d[j] = INF;
                } else {
                    // 算出最小的侧跳
                    min = Math.min(min, d[j]);
                }
            }
            // 计算跳到当前位置的最小次数 并放到d中
            for (int k = 0; k < 3; k++) {
                if (obstacles[i] - 1 == k) {
                    continue; // 这个道路有障碍
                }
                // 没有障碍就比较直跳 跟侧跳的值
                d[k] = Math.min(d[k], min+1);
            }
        }
        return Math.min(Math.min(d[0], d[1]), d[2]);

    }

}
